package com.lxl.heap;

import java.util.Arrays;

/**
 * @Classname HeapSort
 * @Description 堆排序
 * 时间复杂度 O(N * logN)
 * @Date 2021/8/23 10:11
 * @Created by LXLDEMO
 */
public class HeapSort {
    public static void main(String[] args) {
        // 测试数据
        int arr[] = {3,6,8,5,9};
        //测试
        maxHeapSort(arr,arr.length);

    }

    /**
     * 堆排序
     * @param arr
     * @param len
     */
    public static void maxHeapSort(int[] arr,int len){
        System.out.println("初始数据："+Arrays.toString(arr));
        // 最后一个非叶子结点(len-2)/2  最后一个结点：len-1
        for(int i = len/2 - 1; i>=0; i--){
            System.out.println("父结点下标："+i);
            maxHeapify(arr,i,len - 1);
        }
        // 建堆完毕后结果输出
        System.out.println("建堆完毕后结果："+Arrays.toString(arr)+"\n");


        // 先将第一个元素和已排好的元素前一位做交换（将最大的元素放到后面，类似于直接插入排序），再重新调整，直到排序完毕
        for (int i = len -1;i>0;i--){
            System.out.println("本次排序范围：0~"+(i-1));
            swap(arr,0,i);
            maxHeapify(arr,0,i-1);
        }

        System.out.println("最终结果："+Arrays.toString(arr));
    }

    /**
     * 建堆
     * @param arr
     * @param start
     * @param end
     */
    public static void maxHeapify(int arr[],int start,int end){
        // 父结点和子结点下标
        int dad = start;
        int son = dad * 2 +1;
        while(son <= end){ // 子结点在范围内
            if (son + 1 <= end && arr[son] < arr[son +1]){
                son++;
            }
            if (arr[dad]>arr[son]){ // 父结点大于子节点 跳出函数
                return;
            } else { // 否则交换父结点，并继续子结点和孙结点比较
                swap(arr,dad,son);
                dad = son;
                son = dad * 2 +1;
            }
            System.out.println("本次交换结果："+Arrays.toString(arr));
        }
    }

    /**
     * 交换函数
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i ,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

}
